package 算法.树;

import com.sun.jmx.remote.internal.ArrayQueue;
import 算法.递归乘法_leetcode面试题0805;

import java.util.*;

public class 从上到下打印二叉树 {
    public static void main(String[] args) {
        TreeNode no3 = new TreeNode(3);
        TreeNode no9 = new TreeNode(9);
        TreeNode no20 = new TreeNode(20);
        TreeNode no15 = new TreeNode(15);
        TreeNode no7 = new TreeNode(7);

        no3.left = no9;
        no3.right = no20;
        no20.left = no15;
        no20.right = no7;
        List<List<Integer>> l = levelOrder(no3);
        System.out.println(l);

    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if(root == null) return lists;
        int num = 0; //分层记数器
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        num ++;

        TreeNode temp;
        List<Integer> tempLis;
        while (true){
            if(queue.isEmpty()) return lists;

            tempLis = new ArrayList<>();

            int j = num;
            num=0;
            for (int i = 0; i < j; i++) {
                temp = queue.poll();
                tempLis.add(temp.val);
                if(temp.left != null) {queue.offer(temp.left);num++;}
                if(temp.right != null) {queue.offer(temp.right);num++;}
            }
            lists.add(tempLis);



        }
    }
}
class TreeNode {
     int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
}
